#include <iostream>
#include <vector>
#include <bitset>

namespace xyl
{
    template <size_t N>
    class bitset
    {
    public:
        bitset()
        {
            _bits.resize(N / 8 + 1, 0);
        }

    public:
        /*将指定比特位标记为1*/
        void set(size_t x)
        {
            size_t i = x / 8; // 算出x位于哪个字节
            size_t j = x % 8; // 算出x位于该字节的哪一位
            _bits[i] |= (1 << j);
        }
        /*将指定比特位标记为0*/
        void reset(size_t x)
        {
            size_t i = x / 8;
            size_t j = x % 8;
            _bits[i] &= (~(1 << j));
        }
        /*判断指定比特位是否为1*/
        bool test(size_t x)
        {
            size_t i = x / 8;
            size_t j = x % 8;
            return _bits[i] & (1 << j);
        }

    private:
        std::vector<char> _bits;
    };

/*两个位图结构，可表示4种状态*/
template <size_t N>
class twobitset
{
public:
    /*设置对应位置的比特位，x每出现一次就调用一次set()，
        使得出现0次的为00，出现1次的为01，出现2次的为10，出现大于2次的为11。*/
    void set(size_t x)
    {
        if (!_bs1.test(x) && !_bs2.test(x)) // 第一次出现，00->01
            _bs1.set(x);
        else if (_bs1.test(x)) // 第二次出现，01->10
        {
            _bs1.reset(x);
            _bs2.set(x);
        }
        else if (!_bs1.test(x) && _bs2.test(x)) // 第三次出现，10->11
            _bs1.set(x);
        else if (_bs1.test(x) && _bs2.test(x)) // 11->11
            ;
    }
    /*检测x是否在twobitset中，即检测x是否出现过*/
    bool test(size_t x)
    {
        return _bs1.test(x) && _bs2.test(x);
    }
    /*打印出只出现一次的数*/
    void PrintOnce()
    {
        std::cout << "只出现一次的数：";
        for (size_t i = 0; i < N; ++i)
            if (_bs1.test(i) && !_bs2.test(i))
                std::cout << i << " ";
        std::cout << std::endl;
    }
    /*打印出现两次的数*/
    void PrintTwice()
    {
        std::cout << "出现两次的数：";
        for (size_t i = 0; i < N; ++i)
            if (!_bs1.test(i) && _bs2.test(i))
                std::cout << i << " ";
        std::cout << std::endl;
    }
    /*打印出现大于2次的数*/
    void PrintMoreThanTwice()
    {
        std::cout << "出现大于两次的数：";
        for (size_t i = 0; i < N; ++i)
            if (_bs1.test(i) && _bs2.test(i))
                std::cout << i << " ";
        std::cout << std::endl;
    }

private:
    std::bitset<N> _bs1;
    std::bitset<N> _bs2;
};

void test()
{
    twobitset<100> tbs;
    int a[] = {1, 2, 3, 4, 4, 5, 5, 5, 9, 0, 10, 20};
    for (auto &e : a)
    {
        tbs.set(e);
    }
    tbs.PrintOnce();
    tbs.PrintTwice();
    tbs.PrintMoreThanTwice();

    std::cout << "5是否出现过：" << tbs.test(5) << std::endl;
    std::cout << "66是否出现过：" << tbs.test(66) << std::endl;
}
}

int main()
{
    xyl::test();
    return 0;
}